package org.breathe.internal;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author: breathe
 * @createTime: 2025-05-15
 */
@Slf4j
public class SkipList<T extends Comparable<T>> {
    /**
     * max level
     */
    private static final int MAX_LEVEL = 32;

    /**
     * generate a new level that random
     */
    private static final double P = 0.25;
    private SkipListNode<T> head;
    private int level;
    private int size;
    private Random random;
    private SkipListNode<T> tail;
    public static class SkipListNode<T> {
        public double score;
        public T member;
        SkipListNode<T> backward;
        SkipListLevel[] levels;
        public SkipListNode(int levelSize, double score, T member) {
            this.levels = new SkipListLevel[levelSize];
            for (int i = 0; i < levelSize; i ++) {
                this.levels[i] = new SkipListLevel(null, 0);
            }
            this.score = score;
            this.member = member;
            this.backward = null;
        }
        public static class SkipListLevel<T> {
            SkipListNode<T> forward;
            long span;
            public SkipListLevel(SkipListNode<T> forward, long span) {
                this.forward = forward;
                this.span = span;
            }
        }
    }
    public SkipList() {
        head = new SkipListNode<>(MAX_LEVEL, Double.NEGATIVE_INFINITY, null);
        level = 1;
        size = 0;
        this.random = new Random();
    }
    public SkipListNode<T> insert(double score, T member) {
        //create update array
        SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL];
        long[] rank = new long[MAX_LEVEL];
        SkipListNode<T> x = head;
        int i;
        for (i = level - 1; i >= 0; i --) {
            rank[i] = i == level - 1 ? 0 : rank[i + 1];
            getPositionToInsert(score, member, x, i, update, rank);
            //to judge need?
            //update[i] = x;
        }
        //calculate new level
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (i = level; i < newLevel; i ++) {
                rank[i] = 0;
                update[i] = head;
                update[i].levels[i].span = size;
            }
            level = newLevel;
        }
        //create new node
        x = new SkipListNode<>(newLevel, score, member);
        for (i = 0; i < newLevel; i ++) {
            x.levels[i].forward = update[i].levels[i].forward;
            update[i].levels[i].forward = x;
            x.levels[i].span = update[i].levels[i].span - (rank[0] - rank[i]);
            update[i].levels[i].span = (rank[0] - rank[i]) + 1;
        }
        for (i = newLevel; i < level; i ++) {
            update[i].levels[i].span ++;
        }
        x.backward = update[0] == this.head ? null : update[0];
        if (x.levels[0].forward != null) {
            x.levels[0].forward.backward = x;
        } else {
            tail = x;
        }
        size ++;
        return x;
    }

    private int randomLevel() {
        int level = 1;
        while (random.nextDouble() < P && level < MAX_LEVEL) {
            level ++;
        }
        return level;
    }

    //find position that current node
    //1. suffix node isn't null
    //2. suffix node's score less than insert's node
    //3. if suffix node's score equals current's score, but it's member less than insert's member, to insert
    private SkipListNode<T> getPositionToInsert(double score, T member, SkipListNode<T> x, int i, SkipListNode<T>[] update, long[] rank) {
        while (x.levels[i].forward != null && ((x.levels[i].forward.score < score) || (x.levels[i].forward.score == score && compare((T)x.levels[i].forward.member, member) < 0))) {
            rank[i] += x.levels[i].span;
            x = x.levels[i].forward;
        }
        update[i] = x;
        return x;
    }
    private SkipListNode<T> getPositionToDelete(double score, T member, SkipListNode<T> x, int i, SkipListNode<T>[] update) {
        while (x.levels[i].forward != null && ((x.levels[i].forward.score < score) || (x.levels[i].forward.score == score && compare((T)x.levels[i].forward.member, member) < 0))) {
            x = x.levels[i].forward;
        }
        update[i] = x;
        return x;
    }
    private int compare(T o1, T o2) {
        if (o1 == null || o2 == null) {
            throw new NullPointerException("can't be null");
        }
        return o1.compareTo(o2);
    }
    public boolean delete(double score, T member) {
        SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL];
        SkipListNode<T> x = head;
        int i;
        for (i = level - 1; i >= 0; i --) {
            x = getPositionToDelete(score, member, x, i, update);
        }
        x = x.levels[0].forward;
        if (x != null && x.score == score && compare((T)x.member, member) == 0) {
            skipListDelete(x, update);
            return true;
        }
        return false;
    }

    private void skipListDelete(SkipListNode<T> x, SkipListNode<T>[] update) {
        int i;
        for (i = 0; i < level; i ++) {
            if (update[i].levels[i].forward == x) {
                update[i].levels[i].span += x.levels[i].span - 1;
                update[i].levels[i].forward = x.levels[i].forward;
            } else {
                update[i].levels[i].span --;
            }
        }
        if (x.levels[0].forward != null) {
            x.levels[0].forward.backward = x.backward;
        } else {
            tail = x.backward;
        }
        //check empty level, delete empty level
        while (level > 1 && head.levels[level - 1].forward == null) {
            level --;
        }
        size --;
    }
    public List<SkipListNode<T>> getElementByRankRange(long start, long end){
        List<SkipListNode<T>> list = new ArrayList<>();
        if (size == 0 || start > end || start >= size) {
            return list;
        }

        start = Math.max(0, start);
        end = Math.min(end, size - 1);

        long startRank = start + 1;
        long endRank = end + 1;

        if (startRank > size || endRank < 1) {
            return list;
        }

        SkipListNode<T> x = head;
        if (x == null) {
            return list;
        }

        long traversed = 0;

        for (int i = level - 1; i >= 0; i--) {
            while (x != null && x.levels != null && x.levels.length > i &&
                    x.levels[i] != null && x.levels[i].forward != null &&
                    (traversed + x.levels[i].span) <= startRank - 1) {
                traversed += x.levels[i].span;
                x = x.levels[i].forward;
            }
        }

        if (x != null && x.levels != null && x.levels.length > 0 &&
                x.levels[0] != null && x.levels[0].forward != null) {
            x = x.levels[0].forward;
            traversed++;
        } else {
            return list;
        }

        while (x != null && traversed <= endRank) {
            list.add(x);
            if (x.levels != null && x.levels.length > 0 &&
                    x.levels[0] != null && x.levels[0].forward != null) {
                x = x.levels[0].forward;
                traversed++;
            } else {
                break;
            }
        }

        return list;
    }
    public SkipListNode<T> getElementByRank(long rank) {
        if (rank <= 0 || rank > size) {
            return null;
        }
        SkipListNode<T> x = head;
        long traversed = 0;
        for (int i = level - 1; i >= 0; i --) {
            while (x.levels[i].forward != null && traversed + x.levels[i].span <= rank) {
                traversed += x.levels[i].span;
            }
            if (traversed == rank) {
                return x;
            }
        }
        return null;
    }
    //TODO 	reverse
    public List<SkipListNode<T>> getElementByScoreRange(double min, double max) {
        List<SkipListNode<T>> list = new ArrayList<>();
        SkipListNode<T> x = head;
        for (int i = level - 1; i >= 0; i --) {
            while (x.levels[i].forward != null && x.levels[i].forward.score < min) {
                x = x.levels[i].forward;
            }
        }
        x = x.levels[0].forward;
        while (x != null && x.score <= max) {
            list.add(x);
            x = x.levels[0].forward;
        }
        return list;
    }
}